11088 - End up with more teams/11088.3.cpp

   1 /*
   2   Problem: 11088 - End up with More Teams
   3   Author: Andrés Mejía-Posada
   4
   5   Trying another approach...
   6   Time-limit exceeded + wrong answer
   7  */
   8
   9 #include <algorithm>
  10 #include <iostream>
  11 #include <iterator>
  12 #include <sstream>
  13 #include <fstream>
  14 #include <cassert>
  15 #include <climits>
  16 #include <cstdlib>
  17 #include <cstring>
  18 #include <string>
  19 #include <cstdio>
  20 #include <vector>
  21 #include <cmath>
  22 #include <queue>
  23 #include <deque>
  24 #include <stack>
  25 #include <map>
  26 #include <set>
  27 using namespace std;
  28
  29 #define D(x) cout << #x " is " << x << endl
  30 #define bit(i, n) (n & (1 << i))
  31
  32 int x[15], p[15], n, ans;
  33
  34 bool used[15];
  35
  36 void search(int teams, int person, int first){
  37   //printf("t = %d, p = %d, f = %d\n", teams, person, first);
  38   //for (int i=0; i<person; ++i) cout << p[i] << " "; cout << endl;
  39   ans = max(ans, teams);
  40
  41   for (int i=first; i<n; ++i){
  42     if (!used[i]){
  43       p[person] = i;
  44       used[i] = true;
  45       if (person % 3 < 2){
  46         search(teams, person+1, i+1);
  47       }else if (x[p[person-2]] + x[p[person-1]] + x[i] >= 20){
  48         search(teams + 1, person+1, p[person-2]);
  49       }
  50       used[i] = false;
  51     }
  52   }
  53 }
  54
  55 int main(){
  56   int pizza = 1;
  57   while (scanf("%d", &n) == 1 && n){
  58     for (int i = 0; i<n; ++i) scanf("%d", &x[i]);
  59     sort(x, x+n);
  60     memset(used, 0, sizeof used);
  61     search(0, 0, 0);
  62     printf("Case %d: %d\n", pizza++, ans);
  63   }
  64
  65   return 0;
  66 }